﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ArgusPCLib.BitConversion;
using Word = System.UInt32;

namespace ArgusPCLib.Mathematics
{
	/// <summary>
	/// Class to manipulate an unlimited number of bits, can be used as an unsigned integer with unlimited size.
	/// Be careful: Arguments of type <see cref="int"/> and <see cref="long"/> are interpreted as words of
	/// 32, respectivly 64 bit and not as signed integers.
	/// </summary>
	public class BitManager
	{
		#region Fields
		public const int WordSize = sizeof(Word) * 8;
		List<Word> bits;
		#endregion

		#region Constructors
		public BitManager(IEnumerable<int> words)
		{
			this.bits = new List<Word>();
			if (words != null)
			{
				foreach (int w in words)
					this.bits.Add((Word)w);
			}
			this.Words = new WordCollection(this);
			this.Bits = new BitCollection(this);
		}

		public BitManager(BitManager bitManager)
			:this((IEnumerable<int>)null)
		{
			this.bits.AddRange(bitManager.bits);
		}

		public BitManager(int size)
			: this(new int[size]) { }

		public BitManager()
			: this(1) { }
		#endregion

		#region Properties
		public int Length { get { return this.bits.Count; } }
		public int BitLength { get { return BitManager.WordSize * this.Length; } }

		public int this[int index]
		{
			get
			{
				if (index < this.Length)
					return (int)this.bits[index];
				return 0;
			}
			set
			{
				if (index >= this.Length)
				{
					if (value == 0)
						return;
					this.bits.AddRange(new Word[index - this.Length + 1]);
				}
				this.bits[index] = (Word)value;
			}
		}
		public WordCollection Words { get; private set; }
		public BitCollection Bits { get; private set; }

		/// <summary>
		/// Most significant bit.
		/// This value is equal to <see cref="Bits"/>[<see cref="BitLength"/>-1]
		/// </summary>
		public bool MSB
		{
			get
			{
				if (this.Length < 1)
					return false;
				Word mask = 1u << (BitManager.WordSize - 1);
				return (this.bits.Last() & mask) == mask;
			}
		}

		/// <summary>
		/// Least signifacnt bit.
		/// This value is equal to <see cref="Bits"/>[0]
		/// </summary>
		public bool LSB
		{
			get
			{
				if (this.Length < 1)
					return false;
				return (this.bits[0] & 1u) == 1u;
			}
		}
		#endregion

		#region Public Methods
		#region Various
		public static BitManager From32Bits(int bits)
		{
			BitManager RetVal = new BitManager(1);
			RetVal[0] = bits;
			return RetVal;
		}

		public static BitManager From64Bits(long bits)
		{
			BitManager RetVal = new BitManager(2);
			RetVal.Add(bits);
			return RetVal;
		}

		public void CopyTo(int[] array, int index)
		{
			for (int i = 0; i < this.bits.Count; i++)
				array[i + index] = (int)this.bits[i];
		}

		public int[] ToArray()
		{
			int[] RetVal = new int[this.bits.Count];
			this.CopyTo(RetVal, 0);
			return RetVal;
		}

		public override string ToString()
		{
			StringBuilder sb = new StringBuilder(this.BitLength + this.Length);
			for (int i = this.BitLength - 1; i > -1; i--)
			{
				if (this.Bits[i] == true)
					sb.Append('1');
				else
					sb.Append('0');
			}
			for (int i = this.Length - 1; i > 0; i--)
			{
				sb.Insert(i * BitManager.WordSize, ' ');
			}
			return sb.ToString();
		}

		public void Clear() { this.bits.Clear(); }

		public override bool Equals(object obj)
		{
			return (this == obj as BitManager);
		}
		#endregion

		#region Bitwise Operations
		/// <summary>
		/// Performs logical left shift.
		/// </summary>
		public void LLS(int count)
		{
			if (count < 0)
				throw new ArgumentOutOfRangeException();

			int zeros = count / BitManager.WordSize;
			int shift = count % BitManager.WordSize;

			if (shift > 0)
			{
				if (this.bits.Count < 1)
				{
					this.bits.Add(0u);
				}
				else
				{
					int shiftRight = BitManager.WordSize - shift;
					Word last = this.bits.Last() >> shiftRight;

					for (int i = this.bits.Count - 1; i > 0; i--)
					{
						this.bits[i] = (this.bits[i] << shift) | (this.bits[i - 1] >> shiftRight);
					}
					this.bits[0] <<= shift;

					if (last != 0u)
						this.bits.Add(last);
				}
			}

			if (zeros > 0)
				this.bits.InsertRange(0, new Word[zeros]);
		}

		/// <summary>
		/// Performs logical right shift.
		/// </summary>
		public void LRS(int count)
		{
			if (count < 0)
				throw new ArgumentOutOfRangeException();

			int zeros = System.Math.Min(count / BitManager.WordSize, this.bits.Count);
			int shift = count % BitManager.WordSize;

			if (zeros > 0)
				this.bits.RemoveRange(0, zeros);

			if (shift > 0 && this.bits.Count > 0)
			{
				int shiftLeft = BitManager.WordSize - shift;

				for (int i = 0; i < this.bits.Count - 1; i++)
				{
					this.bits[i] = (this.bits[i] >> shift) | (this.bits[i + 1] << shiftLeft);
				}
				this.bits[this.bits.Count - 1] >>= shift;
			}

			if (zeros > 0)
				this.bits.AddRange(new Word[zeros]);
		}

		/// <summary>
		/// Performs a logical left shift and fills the new bits with
		/// the bits from <paramref name="word"/>, starting with the
		/// most significant bit.
		/// </summary>
		/// <param name="word"></param>
		/// <param name="bitCount"></param>
		public void Insert(int word, int bitCount)
		{
			if (bitCount > BitManager.WordSize || bitCount < 1)
				throw new ArgumentOutOfRangeException("bitCount", "Most not be greater than BitManager.WordSize or smaller than 1.");
			this.bits.Insert(0, (Word)word);
			if (bitCount < BitManager.WordSize)
				this.LRS(BitManager.WordSize - bitCount);
		}

		public void Insert(int word)
		{
			this.bits.Insert(0, (Word)word);
		}

		public void Insert(long dWord)
		{
			Word[] w = new Word[2];
			w[0] = (Word)dWord.ToUInt64();
			w[1] = (Word)(dWord.ToUInt64() >> BitManager.WordSize);
			this.bits.InsertRange(0, w);
		}

		public void Insert(long dWord, int bitCount)
		{
			if (bitCount > 2*BitManager.WordSize || bitCount < 1)
				throw new ArgumentOutOfRangeException("bitCount", "Most not be greater than BitManager.WordSize or smaller than 1.");
			this.Insert(dWord);
			if (bitCount < 2 * BitManager.WordSize)
				this.LRS(2 * BitManager.WordSize - bitCount);
		}

		public void Insert(bool bit)
		{
			this.LLS(1);
			if (bit == true)
				this.bits[0] |= 1u;
		}

		/// <summary>
		/// Removes all leading words which are equal to 0 (zero).
		/// </summary>
		/// <returns>Number of removed words.</returns>
		public int TrimLeadingWords()
		{
			int count = 0;
			while (this.bits.Count > 0 && this.bits.Last() == 0u)
			{
				this.bits.RemoveLast();
				count++;
			}
			return count;
		}

		/// <summary>
		/// Removes all trailing words which are equal to 0 (zero).
		/// </summary>
		/// <returns>Number of removed words.</returns>
		public int TrimTrailingWords()
		{
			int count = 0;
			while (this.bits.Count > 0 && this.bits[0] == 0u)
			{
				this.bits.RemoveAt(0);
				count++;
			}
			return count;
		}

		public void BitwiseNot()
		{
			for (int i = 0; i < this.Length; i++)
				this.bits[i] = ~this.bits[i];
		}

		public void BitwiseAnd(BitManager bitManager)
		{
			if (this.Length > bitManager.Length)
				this.bits.RemoveRange(bitManager.Length, this.Length - bitManager.Length);
			for (int i = 0; i < this.Length; i++)
				this.bits[i] = this.bits[i] & bitManager.bits[i];
		}

		public void BitwiseOr(BitManager bitManager)
		{
			int count;
			if (this.Length < bitManager.Length)
			{
				for (int i = this.Length; i < bitManager.Length; i++)
					this.bits.Add(bitManager.bits[i]);
				count = this.Length;
			}
			else
			{
				count = bitManager.Length;
			}
			for (int i = 0; i < count; i++)
				this.bits[i] = this.bits[i] | bitManager.bits[i];
		}

		public void BitwiseXor(BitManager bitManager)
		{
			int count;
			if (this.Length < bitManager.Length)
			{
				for (int i = this.Length; i < bitManager.Length; i++)
					this.bits.Add(bitManager.bits[i]);
				count = this.Length;
			}
			else
			{
				count = bitManager.Length;
			}
			for (int i = 0; i < count; i++)
				this.bits[i] = this.bits[i] ^ bitManager.bits[i];
		}
		#endregion

		#region Operations
		private void Add(ulong dWord, int index)
		{
			if (index < 0)
				throw new ArgumentOutOfRangeException("index", "Must be greater or equal than 0.");
			if (index >= this.Length)
				this.bits.AddRange(new Word[index - this.Length + 1]);
			ulong val = this.bits[index] + dWord;
			this.bits[index] = (Word)val;
			val >>= BitManager.WordSize;
			if (val != 0ul)
				this.Add(val, index+1);
		}

		public void Add(int word, int index) { this.Add(word.ToUInt64(), index); }
		public void Add(int word) { this.Add(word, 0); }
		public void Add(long dWord, int index) { this.Add(dWord.ToUInt64(), index); }
		public void Add(long dWord) { this.Add(dWord, 0); }

		/// <summary>
		/// Adds a <see cref="BitManager"/> to the current instance.
		/// Both instances are interpreted as unsigned integers.
		/// </summary>
		public void Add(BitManager bitManager)
		{
			for (int i = 0; i < bitManager.Length; i++)
				this.Add((ulong)bitManager.bits[i], i);
		}

		private void Subtract(ulong dWord, int index)
		{
			if (index < 0)
				throw new ArgumentOutOfRangeException("index", "Must be greater or equal than 0.");
			if (index >= this.Length)
				this.bits.AddRange(new Word[index - this.Length + 1]);
			uint r = 0u;
			long val = (long)((ulong)this.bits[index]) - (long)dWord;
			while (val < 0L)
			{
				val += Word.MaxValue;
				r++;
			}
			ulong uval = (ulong)val;
			this.bits[index] = (Word)uval;
			uval = (uval >> BitManager.WordSize) + r;
			index++;
			if (uval != 0ul && index < this.Length)
				this.Subtract(uval, index);
		}

		public void Subtract(int word, int index) { this.Subtract(word.ToUInt64(), index); }
		public void Subtract(int word) { this.Subtract(word, 0); }
		public void Subtract(long doubleWord, int index) { this.Subtract((ulong)doubleWord, index); }
		public void Subtract(long doubleWord) { this.Subtract(doubleWord, 0); }

		/// <summary>
		/// Subtracts a <see cref="BitManager"/> to the current instance.
		/// Both instances are interpreted as unsigned integers.
		/// The behaviour is undefined if the minuend is smaller than the
		/// subtrahend.
		/// </summary>
		public void Subtract(BitManager bitManager)
		{
			if (this.Length < bitManager.Length)
				this.bits.AddRange(new Word[bitManager.Length - this.Length]);
			for (int i = 0; i < bitManager.Length; i++)
				this.Subtract((ulong)bitManager.bits[i], i);
			this.TrimLeadingWords();
		}

		public void Multiply(int word)
		{
			ulong dWord = word.ToUInt64();
			for (int i = this.Length-1; i > -1; i--)
			{
				ulong val = this.bits[i] * dWord;
				this.bits[i] = 0u;
				this.Add(val, i);
			}
			this.TrimLeadingWords();
		}

		public void Multiply(long dWord)
		{
			ulong w0 = (ulong)((Word)dWord);
			ulong w1 = ((ulong)dWord) >> 32;
			for (int i = this.Length - 1; i > -1; i--)
			{
				Word b = this.bits[i];
				this.bits[i] = 0u;
				this.Add(b * w1, i + 1);
				this.Add(b * w0, i);
			}
			this.TrimLeadingWords();
		}

		public void Multiply(BitManager bitManager)
		{
			if (object.ReferenceEquals(this, bitManager))
				bitManager = new BitManager(bitManager);
			int length = this.Length;
			this.bits.AddRange(new Word[bitManager.Length]);
			for (int i = length-1; i > -1; i--)
			{
				ulong thisVal = (ulong)this.bits[i];
				this.bits[i] = 0u;
				for (int j = bitManager.Length-1; j > -1; j--)
				{
					ulong val = thisVal * (ulong)bitManager.bits[j];
					this.Add(val, i + j);
				}
			}
			this.TrimLeadingWords();
		}

		public void Divide(int divisor, out int remainder)
		{
			ulong r = 0u;
			Word d = (Word)divisor;
			for (int i = this.Length - 1; i > -1; i--)
			{
				Word word = 0u;
				for (int j = BitManager.WordSize - 1; j > -1; j--)
				{
					Word mask = 1u << j;
					r <<= 1;
					r |= (this.bits[i] & mask) >> j;
					if (d <= r)
					{
						r -= d;
						word |= mask;
					}
				}
				this.bits[i] = word;
			}
			remainder = r.ToInt32();
			this.TrimLeadingWords();
		}

		public void Divide(long divisor, out long remainder)
		{
			ulong r = 0u;
			ulong d = (ulong)divisor;
			for (int i = this.Length - 1; i > -1; i--)
			{
				Word word = 0u;
				for (int j = BitManager.WordSize - 1; j > -1; j--)
				{
					Word mask = 1u << j;
					r <<= 1;
					r |= (this.bits[i] & mask) >> j;
					if (d <= r)
					{
						r -= d;
						word |= mask;
					}
				}
				this.bits[i] = word;
			}
			remainder = (long)r;
			this.TrimLeadingWords();
		}

		public void Divide(BitManager divisor, out BitManager remainder)
		{
			if (divisor == this)
			{
				remainder = new BitManager();
				this.Clear();
				this.Insert(1);
				return;
			}
			if (divisor > this)
			{
				remainder = new BitManager(this);
				this.Clear();
				return;
			}
			remainder = new BitManager(1);
			for (int i = this.Length-1; i > -1; i--)
			{
				Word word = 0u;
				for (int j = BitManager.WordSize-1; j > -1; j--)
				{
					Word mask = 1u<<j;
					remainder.Insert((this.bits[i] & mask) == mask);
					if (divisor == remainder)
					{
						remainder.bits.Clear();
						word |= mask;
					}
					else if (divisor < remainder)
					{
						remainder.Subtract(divisor);
						word |= mask;
					}
				}
				this.bits[i] = word;
			}
			this.TrimLeadingWords();
			remainder.TrimLeadingWords();
		}
		#endregion
		#endregion

		#region Operators
		public static bool operator ==(BitManager bm, int word)
		{
			if (bm.Length < 1)
				return word == 0;
			if (bm[0] != word)
				return false;
			for (int i = 1; i < bm.Length; i++)
			{
				if (bm.bits[i] != 0u)
					return false;
			}
			return true;
		}

		public static bool operator ==(BitManager bm, long dWord)
		{
			if (bm.Length < 1)
				return dWord == 0L;

			Word w0 = dWord.ToUInt32();
			Word w1 = (Word)(dWord.ToUInt64() >> BitManager.WordSize);

			if (bm.Length < 2)
				return w1 == 0u && bm.bits[0] == w0;
			if (bm.bits[0] != w0 || bm.bits[1] != w1)
				return false;
			for (int i = 2; i < bm.Length; i++)
			{
				if (bm.bits[i] != 0u)
					return false;
			}
			return false;
		}

		public static bool operator ==(BitManager bm1, BitManager bm2)
		{
			if (object.ReferenceEquals(bm1, null) || object.ReferenceEquals(bm2, null))
				return object.ReferenceEquals(bm1, bm2);

			BitManager min, max;
			if (bm1.Length < bm2.Length)
			{
				min = bm1;
				max = bm2;
			}
			else
			{
				min = bm2;
				max = bm1;
			}
			for (int i = min.Length; i < max.Length; i++)
			{
				if (max.bits[i] != 0u)
					return false;
			}
			for (int i = 0; i < min.Length; i++)
			{
				if (min.bits[i] != max.bits[i])
					return false;
			}
			return true;
		}

		public static bool operator !=(BitManager bm, int word)
		{
			return !(bm == word);
		}

		public static bool operator !=(BitManager bm, long dWord)
		{
			return !(bm == dWord);
		}

		public static bool operator !=(BitManager bm1, BitManager bm2)
		{
			return !(bm1 == bm2);
		}

		public static bool operator <(BitManager bm, int word)
		{
			if (bm.Length < 1)
				return word > 0;

			if (bm.bits[0] >= (Word)word)
				return false;

			for (int i = 1; i < bm.Length; i++)
			{
				if (bm.bits[i] != 0u)
					return false;
			}
			return true;
		}

		public static bool operator <(BitManager bm, long dWord)
		{
			if (bm.Length < 1)
				return dWord > 0L;

			Word w1 = (Word)(dWord.ToUInt64() >> BitManager.WordSize);

			if (bm.Length < 2 && w1 > 0)
				return true;

			ulong dW = ((ulong)bm.bits[1] << BitManager.WordSize) | bm.bits[0];

			if (dW >= dWord.ToUInt64())
				return false;

			for (int i = 2; i < bm.Length; i++)
			{
				if (bm.bits[i] != 0u)
					return false;
			}
			return true;
		}

		public static bool operator >(BitManager bm, int word)
		{
			if (bm.Length < 1)
				return false;

			for (int i = 1; i < bm.Length; i++)
			{
				if (bm.bits[i] != 0u)
					return true; ;
			}

			if (bm.bits[0] > (Word)word)
				return true;

			return false;
		}

		public static bool operator >(BitManager bm, long dWord)
		{
			if (bm.Length < 1)
				return false;

			for (int i = 2; i < bm.Length; i++)
			{
				if (bm.bits[i] != 0u)
					return true; ;
			}

			ulong dW = bm.bits[0];
			if (bm.Length > 1)
				dW |= ((ulong)bm.bits[1] << BitManager.WordSize);

			if (dW > dWord.ToUInt64())
				return true;

			return false;
		}

		public static bool operator <(BitManager bm1, BitManager bm2)
		{
			if (object.ReferenceEquals(bm1, null) || object.ReferenceEquals(bm2, null))
				throw new ArgumentNullException();

			BitManager min, max;
			if (bm1.Length < bm2.Length)
			{
				min = bm1;
				max = bm2;
			}
			else
			{
				min = bm2;
				max = bm1;
			}
			for (int i = min.Length; i < max.Length; i++)
			{
				if (max.bits[i] != 0u)
					return bm1.Length < bm2.Length;
			}
			for (int i = min.Length-1; i > -1; i--)
			{
				if (bm1.bits[i] < bm2.bits[i])
					return true;
			}
			return false;
		}

		public static bool operator >(BitManager bm1, BitManager bm2)
		{
			if (object.ReferenceEquals(bm1, null) || object.ReferenceEquals(bm2, null))
				throw new ArgumentNullException();

			BitManager min, max;
			if (bm1.Length < bm2.Length)
			{
				min = bm1;
				max = bm2;
			}
			else
			{
				min = bm2;
				max = bm1;
			}
			for (int i = min.Length; i < max.Length; i++)
			{
				if (max.bits[i] != 0u)
					return bm1.Length > bm2.Length;
			}
			for (int i = min.Length - 1; i > -1; i--)
			{
				if (bm1.bits[i] > bm2.bits[i])
					return true;
			}
			return false;
		}

		public static bool operator <=(BitManager bm1, BitManager bm2)
		{
			return (bm1 < bm2 || bm1 == bm2);
		}

		public static bool operator >=(BitManager bm1, BitManager bm2)
		{
			return (bm1 > bm2 || bm1 == bm2);
		}

		public static bool operator <=(BitManager bm, int word)
		{
			return (bm < word || bm == word);
		}

		public static bool operator >=(BitManager bm, int word)
		{
			return (bm > word || bm == word);
		}

		public static bool operator <=(BitManager bm, long dWord)
		{
			return (bm < dWord || bm == dWord);
		}

		public static bool operator >=(BitManager bm, long dWord)
		{
			return (bm > dWord || bm == dWord);
		}
		#endregion

		#region Subtypes
		public class WordCollection : IntIndexedProperty<int>
		{
			BitManager bits;
			public WordCollection(BitManager bits)
				:base()
			{
				this.bits = bits;
			}

			public override int Count { get { return this.bits.Length; } }
			public override int this[int index] { get { return this.bits[index]; } set { this.bits[index] = value; } }
		}

		public class BitCollection : IntIndexedProperty<bool>
		{
			BitManager bits;

			public BitCollection(BitManager bits)
			{
				this.bits = bits;
			}

			public override int Count { get { return this.bits.BitLength; } }

			public override bool this[int index]
			{
				get
				{
					int wIndex = index / BitManager.WordSize;
					int bIndex = index % BitManager.WordSize;
					int word = this.bits[wIndex];
					int mask = 1 << bIndex;
					return (word & mask) == mask;
				}
				set
				{
					int wIndex = index / BitManager.WordSize;
					int bIndex = index % BitManager.WordSize;
					int word = this.bits[wIndex];
					int mask = 1 << bIndex;
					if (value == true)
						this.bits[wIndex] |= mask;
					else
						this.bits[wIndex] &= ~mask;
				}
			}

			public int IndexOf(bool bit) { return this.IndexOf(bit, 0); }

			public int IndexOf(bool bit, int startIndex)
			{
				for (int i = startIndex; i < this.Count; i++)
				{
					if (this[i] == bit)
						return i;
				}
				return -1;
			}

			public int LastIndexOf(bool bit) { return this.LastIndexOf(bit, this.Count - 1); }

			public int LastIndexOf(bool bit, int startIndex)
			{
				for (int i = startIndex; i > -1; i--)
				{
					if (this[i] == bit)
						return i;
				}
				return -1;
			}
		}
		#endregion
	}
}
